//Sort a linked list in O(n log n) time using constant space complexity. 
//
// Example 1: 
//
// 
//Input: 4->2->1->3
//Output: 1->2->3->4
// 
//
// Example 2: 
//
// 
//Input: -1->5->3->4->0
//Output: -1->0->3->4->5 
// Related Topics 排序 链表


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun sortList(head: ListNode?): ListNode? {
        if(head== null || head.next == null){
            return head
        }
        var slow = head
        var fast = head
        while (fast?.next?.next != null){
            fast = fast?.next?.next
            slow = slow?.next
        }
        val right = slow?.next
        slow?.next = null
        var p = sortList(head)
        var q = sortList(right)
        //merge
        val fakeHead = ListNode(0)
        var current = fakeHead
        while (p != null && q != null) {
            if(p.`val`>= q.`val`){
                current.next = q
                current = q
                q = q?.next
            }else{
                current.next = p
                current = p
                p = p?.next
            }
        }
        p?.let { current.next = it }
        q?.let { current.next = it }
       return fakeHead.next

    }
}
//leetcode submit region end(Prohibit modification and deletion)
